//“图的最短路径”
//“迪杰斯特拉算法的原理”

//以下是一个使用 JavaScript 实现迪杰斯特拉算法的基本示例。在这个例子中，我们使用一个邻接列表表示带权重的图，并用一个优先队列（这里用数组模拟，实际应用中可以考虑使用更高效的最小堆实现）来辅助计算。

// 假设我们有一个邻接列表表示的有向图，其中每个节点包含到其他节点的边及其权重
const graph = {
    'A': { 'B': 1, 'C': 4 },
    'B': { 'A': 1, 'D': 2, 'E': 5 },
    'C': { 'A': 4, 'F': 3 },
    'D': { 'B': 2, 'E': 1 },
    'E': { 'B': 5, 'D': 1, 'F': 6 },
    'F': { 'C': 3, 'E': 6 }
  };
  
  function dijkstra(startNode, graph) {
    const distances = {};
    const visited = {};
    const queue = [];
  
    // 初始化距离和已访问集合
    for (const node in graph) {
      if (node === startNode) {
        distances[node] = 0;
      } else {
        distances[node] = Infinity;
      }
      visited[node] = false;
      queue.push({ node, distance: distances[node] });
    }
  
    while (queue.length > 0) {
      // 获取当前已知距离最小的顶点
      queue.sort((a, b) => a.distance - b.distance);
      const currentNode = queue.shift().node;
  
      // 如果当前节点已经访问过，则跳过
      if (visited[currentNode]) continue;
      visited[currentNode] = true;
  
      // 更新相邻节点的距离值
      for (const neighbor in graph[currentNode]) {
        const weight = graph[currentNode][neighbor];
        const altPath = distances[currentNode] + weight;
  
        if (altPath < distances[neighbor]) {
          distances[neighbor] = altPath;
          queue.push({ node: neighbor, distance: altPath });
        }
      }
    }
  
    return distances;
  }
  
  // 从节点 'A' 开始计算最短路径
  console.log(dijkstra('A', graph));